package net.sf.calibur.test.misc;

import net.sf.calibur.util.BinaryHeap;
import static java.lang.System.*;

public class SearchBinaryHeap {
	private static int[] dump(BinaryHeap<Integer> bh) {
		int size = bh.size();
		int[] data = new int[size];
		for (int i = 0; i < size; ++i) {
			data[i] = bh.getAt(i);
			out.print(bh.getAt(i));
			out.print(' ');
		}
		out.println();
		
		return data;
	}
	
	
	public static void main(String[] args) {
		BinaryHeap<Integer> bh = new BinaryHeap<Integer>(); 
		bh.add(5);
		dump(bh);
		bh.add(3);
		dump(bh);
		bh.add(7);
		dump(bh);
		bh.add(1);
		dump(bh);
		bh.add(2);
		bh.add(8);
		bh.add(4);
		bh.add(6);
		dump(bh);
		
		int idx = bh.indexOf(7);
		bh.setAt(idx, 0);
		bh.modifiedAt(idx);
		bh.setAt(1, 9);
		bh.modifiedAt(1);
		bh.add(0);
		int[] data = dump(bh);
		
		out.println(search(data, 5));
		out.println(search(data, 0));
		out.println(search(data, 10));
	}
	
	private static int search(int data[], int v) {
		int size = data.length;
		int k = size >> 1;
		int diff = 0;
		while (k > 0 && k < size) {
			diff = v - data[k];
			if (diff == 0) {
				return k;
			} else if (diff < 0) {
				k = (k - 1) >> 1;
			} else {
				k = (k << 1) + 1;
			}
		}
		
		return -1;
	}

}
